Abstract: Locally decodable codes (LDCs) are error-correcting codes that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. Despite importance of these objects, the best known constructions of constant query LDCs have super-polynomial length, and there is a significant gap between the best constructions and the known lower bounds in terms of the block length.

For many applications it suffices to consider the weaker notion of relaxed LDCs (RLDCs), introduced by Ben-Sasson et al. [BGH+06], which allows the local decoding algorithm to abort if by querying a few bits it detects that the input is not a codeword. This relaxation turned out to allow decoding algorithms with constant query complexity for codes with almost linear length.

In this talk, I will present a new RLDC construction which improves the parameters of [BGH+06]. This construction matches (up to a multiplicative constant factor) the lower bounds of Katz and Trevisan [KT00] and Woodruff [Woo07] for constant query LDCs, thus making progress toward understanding the gap between LDCs and RLDCs in the constant query regime.

Based on joint work with Igor Shinkar.